package it.storm.solution;

import java.util.Arrays;

/**
 * 面试题 10.11. 峰与谷
 * https://leetcode-cn.com/problems/peaks-and-valleys-lcci/
 */
public class Solutions_mianshi_10_11 {
    public static void main(String[] args) {
        int[] nums = {5, 3, 1, 2, 3};  // output: {5, 1, 3, 2, 3}
//        int[] nums = {3, 5, 2, 1, 6, 4};  // output: {3, 5, 1, 6, 2, 4}

        wiggleSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 解法二：原地交换（0ms）
     */
    public static void wiggleSort(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        // flag = true，表示前一个元素是峰
        boolean flag = true;
        for (int i = 1; i < nums.length; i++) {
            if (flag) {
                // 前一个是峰，若是当前元素小于前一元素，则做为谷
                // 若是大于，那么两个元素交换
                if (nums[i] > nums[i - 1]) {
                    int t = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = t;
                }
            } else {
                // 前一个是谷，若是当前元素大于前一元素，则做为峰
                // 若是小于，那么两个元素交换
                if (nums[i] < nums[i - 1]) {
                    int t = nums[i];
                    nums[i] = nums[i - 1];
                    nums[i - 1] = t;
                }
            }
            // 峰谷交替
            flag = !flag;
        }
    }

    /**
     * 解法一：排序后，两两交换（3ms）
     */
    public static void wiggleSort2(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        Arrays.sort(nums);
        // 1 2 3 3 5，转化为 2 1 3 3 5
        // 2(峰)，1(谷)，3(峰)，3(谷)，5(峰)
        int len = nums.length;
        for (int i = 0; i < len - 1; i += 2) {
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
    }
}
